home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / util / misc / GadMget1_9.lha / GadMGet1.9 / GadMget1.9.source.lha / tree.c < prev    next >
C/C++ Source or Header  |  1995-02-02  |  11KB  |  545 lines
  1. /* as_tree - tree library for as
  2.  * vix 14dec85 [written]
  3.  * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221]
  4.  * vix 06feb86 [added tree_mung()]
  5.  * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224]
  6.  * vix 23jun86 [added delete uar to add for replaced nodes]
  7.  */
  8.  
  9.  
  10. /* This program text was created by Paul Vixie using examples from the book:
  11.  * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN
  12.  * 0-13-022005-1.  This code and associated documentation is hereby placed
  13.  * in the public domain.
  14.  */
  15.  
  16.  
  17. /*#define        DEBUG    "tree"*/
  18.  
  19.  
  20. #include <stdio.h>
  21. #include <exec/types.h>
  22. #include "vixie.h"
  23. #include "tree.h"
  24.  
  25.  
  26. #ifdef DEBUG
  27. #define        MSG(msg)    printf("DEBUG: '%s'\n", msg);
  28. #else
  29. #define        MSG(msg)
  30. #endif
  31.  
  32. LONG lTreeTicker;
  33. LONG lTreeSubTicker;
  34. extern struct Window *mgetWnd;
  35. char *sTreeWriteHere;
  36. char *szTickerString;
  37.  
  38. void tree_init(ppr_tree)
  39. tree    **ppr_tree;
  40. {
  41.     ENTER("tree_init")
  42.     *ppr_tree = NULL;
  43.     EXITV
  44. }
  45.     
  46.  
  47. char *tree_srch(ppr_tree, pfi_compare, pc_user)
  48. tree    **ppr_tree;
  49. int    (*pfi_compare)();
  50. char    *pc_user;
  51. {
  52.     register int    i_comp;
  53.     /* register tree    *pr_new;  THIS VARIABLE NOT USED -- Jeremy */
  54.  
  55.     ENTER("tree_srch")
  56.  
  57.     if (*ppr_tree)
  58.     {
  59.         i_comp = (*pfi_compare)(pc_user, (**ppr_tree).tree_p);
  60.         if (i_comp > 0)
  61.             EXIT(tree_srch(
  62.                 &(**ppr_tree).tree_r,
  63.                 pfi_compare,
  64.                 pc_user
  65.             ))
  66.         if (i_comp < 0)
  67.             EXIT(tree_srch(
  68.                 &(**ppr_tree).tree_l,
  69.                 pfi_compare,
  70.                 pc_user
  71.             ))
  72.  
  73.         /* not higher, not lower... this must be the one.
  74.          */
  75.         EXIT((**ppr_tree).tree_p)
  76.     }
  77.  
  78.     /* grounded. NOT found.
  79.      */
  80.     EXIT(NULL)
  81. }
  82.  
  83.  
  84. void tree_add(ppr_tree, pfi_compare, pc_user, pfi_delete)
  85. tree    **ppr_tree;
  86. int    (*pfi_compare)();
  87. char    *pc_user;
  88. int    (*pfi_delete)();
  89. {
  90.     void    sprout();
  91.     int    i_balance = FALSE;
  92.  
  93.     if ((lTreeSubTicker >= 100)&&(mgetWnd != NULL)) 
  94.     {
  95.         sprintf(sTreeWriteHere,"%i",lTreeTicker);
  96.         SetWindowTitles(mgetWnd, szTickerString, (char *) ~0); 
  97.         lTreeSubTicker = 0;
  98.         lTreeTicker++;
  99.     }
  100.     
  101.     lTreeSubTicker++;
  102.     
  103.     ENTER("tree_add")
  104.     sprout(ppr_tree, pc_user, &i_balance, pfi_compare, pfi_delete);
  105.     EXITV
  106. }
  107.  
  108.  
  109. static void sprout(ppr, pc_data, pi_balance, pfi_compare, pfi_delete)
  110. tree    **ppr;
  111. char    *pc_data;
  112. int    *pi_balance;
  113. int    (*pfi_compare)();
  114. int    (*pfi_delete)();
  115. {
  116.     tree    *p1, *p2;
  117.     int    cmp;
  118.  
  119.     ENTER("sprout")
  120.  
  121.     /* are we grounded?  if so, add the node "here" and set the rebalance
  122.      * flag, then exit.
  123.      */
  124.     if (!*ppr) {
  125.         MSG("grounded. adding new node, setting h=true")
  126.         *ppr = (tree *) malloc(sizeof(tree));
  127.         (*ppr)->tree_l = NULL;
  128.         (*ppr)->tree_r = NULL;
  129.         (*ppr)->tree_b = 0;
  130.         (*ppr)->tree_p = pc_data;
  131.         *pi_balance = TRUE;
  132.         EXITV
  133.     }
  134.  
  135.     /* compare the data using routine passed by caller.
  136.      */
  137.     cmp = (*pfi_compare)(pc_data, (*ppr)->tree_p);
  138.  
  139.     /* if LESS, prepare to move to the left.
  140.      */
  141.     if (cmp < 0) {
  142.         MSG("LESS. sprouting left.")
  143.         sprout(&(*ppr)->tree_l, pc_data, pi_balance,
  144.             pfi_compare, pfi_delete);
  145.         if (*pi_balance) {    /* left branch has grown longer */
  146.             MSG("LESS: left branch has grown")
  147.             switch ((*ppr)->tree_b)
  148.             {
  149.             case 1:    /* right branch WAS longer; balance is ok now */
  150.                 MSG("LESS: case 1.. balnce restored implicitly")
  151.                 (*ppr)->tree_b = 0;
  152.                 *pi_balance = FALSE;
  153.                 break;
  154.             case 0:    /* balance WAS okay; now left branch longer */
  155.                 MSG("LESS: case 0.. balnce bad but still ok")
  156.                 (*ppr)->tree_b = -1;
  157.                 break;
  158.             case -1:
  159.                 /* left branch was already too long. rebalnce */
  160.                 MSG("LESS: case -1: rebalancing")
  161.                 p1 = (*ppr)->tree_l;
  162.                 if (p1->tree_b == -1) {    /* LL */
  163.                     MSG("LESS: single LL")
  164.                     (*ppr)->tree_l = p1->tree_r;
  165.                     p1->tree_r = *ppr;
  166.                     (*ppr)->tree_b = 0;
  167.                     *ppr = p1;
  168.                 }
  169.                 else {            /* double LR */
  170.                     MSG("LESS: double LR")
  171.  
  172.                     p2 = p1->tree_r;
  173.                     p1->tree_r = p2->tree_l;
  174.                     p2->tree_l = p1;
  175.  
  176.                     (*ppr)->tree_l = p2->tree_r;
  177.                     p2->tree_r = *ppr;
  178.  
  179.                     if (p2->tree_b == -1)
  180.                         (*ppr)->tree_b = 1;
  181.                     else
  182.                         (*ppr)->tree_b = 0;
  183.  
  184.                     if (p2->tree_b == 1)
  185.                         p1->tree_b = -1;
  186.                     else
  187.                         p1->tree_b = 0;
  188.                     *ppr = p2;
  189.                 } /*else*/
  190.                 (*ppr)->tree_b = 0;
  191.                 *pi_balance = FALSE;
  192.             } /*switch*/
  193.         } /*if*/
  194.         EXITV
  195.     } /*if*/
  196.  
  197.     /* if MORE, prepare to move to the right.
  198.      */
  199.     if (cmp > 0) {
  200.         MSG("MORE: sprouting to the right")
  201.         sprout(&(*ppr)->tree_r, pc_data, pi_balance,
  202.             pfi_compare, pfi_delete);
  203.         if (*pi_balance) {    /* right branch has grown longer */
  204.             MSG("MORE: right branch has grown")
  205.  
  206.             switch ((*ppr)->tree_b)
  207.             {
  208.             case -1:MSG("MORE: balance was off, fixed implicitly")
  209.                 (*ppr)->tree_b = 0;
  210.                 *pi_balance = FALSE;
  211.                 break;
  212.             case 0:    MSG("MORE: balance was okay, now off but ok")
  213.                 (*ppr)->tree_b = 1;
  214.                 break;
  215.             case 1:    MSG("MORE: balance was off, need to rebalance")
  216.                 p1 = (*ppr)->tree_r;
  217.                 if (p1->tree_b == 1) {    /* RR */
  218.                     MSG("MORE: single RR")
  219.                     (*ppr)->tree_r = p1->tree_l;
  220.                     p1->tree_l = *ppr;
  221.                     (*ppr)->tree_b = 0;
  222.                     *ppr = p1;
  223.                 }
  224.                 else {            /* double RL */
  225.                     MSG("MORE: double RL")
  226.  
  227.                     p2 = p1->tree_l;
  228.                     p1->tree_l = p2->tree_r;
  229.                     p2->tree_r = p1;
  230.  
  231.                     (*ppr)->tree_r = p2->tree_l;
  232.                     p2->tree_l = *ppr;
  233.  
  234.                     if (p2->tree_b == 1)
  235.                         (*ppr)->tree_b = -1;
  236.                     else
  237.                         (*ppr)->tree_b = 0;
  238.  
  239.                     if (p2->tree_b == -1)
  240.                         p1->tree_b = 1;
  241.                     else
  242.                         p1->tree_b = 0;
  243.  
  244.                     *ppr = p2;
  245.                 } /*else*/
  246.                 (*ppr)->tree_b = 0;
  247.                 *pi_balance = FALSE;
  248.             } /*switch*/
  249.         } /*if*/
  250.         EXITV
  251.     } /*if*/
  252.  
  253.     /* not less, not more: this is the same key!  replace...
  254.      */
  255.     MSG("I found it!  Replacing data value")
  256.     *pi_balance = FALSE;
  257.     if (pfi_delete)
  258.         (*pfi_delete)((*ppr)->tree_p);
  259.     (*ppr)->tree_p = pc_data;
  260.     EXITV
  261. }
  262.  
  263.  
  264. int tree_delete(ppr_p, pfi_compare, pc_user, pfi_uar)
  265. tree    **ppr_p;
  266. int    (*pfi_compare)();
  267. char    *pc_user;
  268. int    (*pfi_uar)();
  269. {
  270.     int    i_balance = FALSE, i_uar_called = FALSE;
  271.  
  272.     ENTER("tree_delete");
  273.     EXIT(delete(ppr_p, pfi_compare, pc_user, pfi_uar,
  274.                 &i_balance, &i_uar_called))
  275. }
  276.  
  277.  
  278. static int delete(ppr_p, pfi_compare, pc_user, pfi_uar,
  279.                         pi_balance, pi_uar_called)
  280. tree    **ppr_p;
  281. int    (*pfi_compare)();
  282. char    *pc_user;
  283. int    (*pfi_uar)();
  284. int    *pi_balance;
  285. int    *pi_uar_called;
  286. {
  287.     void    del(), balanceL(), balanceR();
  288.     tree    *pr_q;
  289.     int    i_comp, i_ret;
  290.  
  291.     ENTER("delete")
  292.  
  293.     if (*ppr_p == NULL) {
  294.         MSG("key not in tree")
  295.         EXIT(FALSE)
  296.     }
  297.  
  298.     i_comp = (*pfi_compare)((*ppr_p)->tree_p, pc_user);
  299.     if (i_comp > 0) {
  300.         MSG("too high - scan left")
  301.         i_ret = delete(&(*ppr_p)->tree_l, pfi_compare, pc_user, pfi_uar,
  302.                         pi_balance, pi_uar_called);
  303.         if (*pi_balance)
  304.             balanceL(ppr_p, pi_balance);
  305.     }
  306.     else if (i_comp < 0) {
  307.         MSG("too low - scan right")
  308.         i_ret = delete(&(*ppr_p)->tree_r, pfi_compare, pc_user, pfi_uar,
  309.                         pi_balance, pi_uar_called);
  310.         if (*pi_balance)
  311.             balanceR(ppr_p, pi_balance);
  312.     }
  313.     else {
  314.         MSG("equal")
  315.         pr_q = *ppr_p;
  316.         if (pr_q->tree_r == NULL) {
  317.             MSG("right subtree null")
  318.             *ppr_p = pr_q->tree_l;
  319.             *pi_balance = TRUE;
  320.         }
  321.         else if (pr_q->tree_l == NULL) {
  322.             MSG("right subtree non-null, left subtree null")
  323.             *ppr_p = pr_q->tree_r;
  324.             *pi_balance = TRUE;
  325.         }
  326.         else {
  327.             MSG("neither subtree null")
  328.             del(&pr_q->tree_l, pi_balance, &pr_q, pfi_uar,
  329.                                 pi_uar_called);
  330.             if (*pi_balance)
  331.                 balanceL(ppr_p, pi_balance);
  332.         }
  333.         free(pr_q);
  334.         if (!*pi_uar_called && pfi_uar)
  335.             (*pfi_uar)(pr_q->tree_p);
  336.         i_ret = TRUE;
  337.     }
  338.     EXIT(i_ret)
  339. }
  340.  
  341.  
  342. static void del(ppr_r, pi_balance, ppr_q, pfi_uar, pi_uar_called)
  343. tree    **ppr_r;
  344. int    *pi_balance;
  345. tree    **ppr_q;
  346. int    (*pfi_uar)();
  347. int    *pi_uar_called;
  348. {
  349.     void    balanceR();
  350.  
  351.     ENTER("del")
  352.  
  353.     if ((*ppr_r)->tree_r != NULL) {
  354.         del(&(*ppr_r)->tree_r, pi_balance, ppr_q, pfi_uar,
  355.                                 pi_uar_called);
  356.         if (*pi_balance)
  357.             balanceR(ppr_r, pi_balance);
  358.     } else {
  359.         if (pfi_uar)
  360.             (*pfi_uar)((*ppr_q)->tree_p);
  361.         *pi_uar_called = TRUE;
  362.         (*ppr_q)->tree_p = (*ppr_r)->tree_p;
  363.         *ppr_q = *ppr_r;
  364.         *ppr_r = (*ppr_r)->tree_l;
  365.         *pi_balance = TRUE;
  366.     }
  367.  
  368.     EXITV
  369. }
  370.  
  371.  
  372. static void balanceL(ppr_p, pi_balance)
  373. tree    **ppr_p;
  374. int    *pi_balance;
  375. {
  376.     tree    *p1, *p2;
  377.     int    b1, b2;
  378.  
  379.     ENTER("balanceL")
  380.     MSG("left branch has shrunk")
  381.  
  382.     switch ((*ppr_p)->tree_b)
  383.     {
  384.     case -1: MSG("was imbalanced, fixed implicitly")
  385.         (*ppr_p)->tree_b = 0;
  386.         break;
  387.     case 0:    MSG("was okay, is now one off")
  388.         (*ppr_p)->tree_b = 1;
  389.         *pi_balance = FALSE;
  390.         break;
  391.     case 1:    MSG("was already off, this is too much")
  392.         p1 = (*ppr_p)->tree_r;
  393.         b1 = p1->tree_b;
  394.         if (b1 >= 0) {
  395.             MSG("single RR")
  396.             (*ppr_p)->tree_r = p1->tree_l;
  397.             p1->tree_l = *ppr_p;
  398.             if (b1 == 0) {
  399.                 MSG("b1 == 0")
  400.                 (*ppr_p)->tree_b = 1;
  401.                 p1->tree_b = -1;
  402.                 *pi_balance = FALSE;
  403.             } else {
  404.                 MSG("b1 != 0")
  405.                 (*ppr_p)->tree_b = 0;
  406.                 p1->tree_b = 0;
  407.             }
  408.             *ppr_p = p1;
  409.         } else {
  410.             MSG("double RL")
  411.             p2 = p1->tree_l;
  412.             b2 = p2->tree_b;
  413.             p1->tree_l = p2->tree_r;
  414.             p2->tree_r = p1;
  415.             (*ppr_p)->tree_r = p2->tree_l;
  416.             p2->tree_l = *ppr_p;
  417.             if (b2 == 1)
  418.                 (*ppr_p)->tree_b = -1;
  419.             else
  420.                 (*ppr_p)->tree_b = 0;
  421.             if (b2 == -1)
  422.                 p1->tree_b = 1;
  423.             else
  424.                 p1->tree_b = 0;
  425.             *ppr_p = p2;
  426.             p2->tree_b = 0;
  427.         }
  428.     }
  429.     EXITV
  430. }
  431.  
  432.  
  433. static void balanceR(ppr_p, pi_balance)
  434. tree    **ppr_p;
  435. int    *pi_balance;
  436. {
  437.     tree    *p1, *p2;
  438.     int    b1, b2;
  439.  
  440.     ENTER("balanceR")
  441.     MSG("right branch has shrunk")
  442.     switch ((*ppr_p)->tree_b)
  443.     {
  444.     case 1:    MSG("was imbalanced, fixed implicitly")
  445.         (*ppr_p)->tree_b = 0;
  446.         break;
  447.     case 0:    MSG("was okay, is now one off")
  448.         (*ppr_p)->tree_b = -1;
  449.         *pi_balance = FALSE;
  450.         break;
  451.     case -1: MSG("was already off, this is too much")
  452.         p1 = (*ppr_p)->tree_l;
  453.         b1 = p1->tree_b;
  454.         if (b1 <= 0) {
  455.             MSG("single LL")
  456.             (*ppr_p)->tree_l = p1->tree_r;
  457.             p1->tree_r = *ppr_p;
  458.             if (b1 == 0) {
  459.                 MSG("b1 == 0")
  460.                 (*ppr_p)->tree_b = -1;
  461.                 p1->tree_b = 1;
  462.                 *pi_balance = FALSE;
  463.             } else {
  464.                 MSG("b1 != 0")
  465.                 (*ppr_p)->tree_b = 0;
  466.                 p1->tree_b = 0;
  467.             }
  468.             *ppr_p = p1;
  469.         } else {
  470.             MSG("double LR")
  471.             p2 = p1->tree_r;
  472.             b2 = p2->tree_b;
  473.             p1->tree_r = p2->tree_l;
  474.             p2->tree_l = p1;
  475.             (*ppr_p)->tree_l = p2->tree_r;
  476.             p2->tree_r = *ppr_p;
  477.             if (b2 == -1)
  478.                 (*ppr_p)->tree_b = 1;
  479.             else
  480.                 (*ppr_p)->tree_b = 0;
  481.             if (b2 == 1)
  482.                 p1->tree_b = -1;
  483.             else
  484.                 p1->tree_b = 0;
  485.             *ppr_p = p2;
  486.             p2->tree_b = 0;
  487.         }
  488.     }
  489.     EXITV
  490. }
  491.  
  492.  
  493. int tree_trav(ppr_tree, pfi_uar)
  494. tree    **ppr_tree;
  495. int    (*pfi_uar)();
  496. {
  497.     ENTER("tree_trav")
  498.  
  499.     if (!*ppr_tree)
  500.         EXIT(TRUE)
  501.  
  502.     if (!tree_trav(&(**ppr_tree).tree_l, pfi_uar))
  503.         EXIT(FALSE)
  504.     if (!(*pfi_uar)((**ppr_tree).tree_p))
  505.         EXIT(FALSE)
  506.     if (!tree_trav(&(**ppr_tree).tree_r, pfi_uar))
  507.         EXIT(FALSE)
  508.         
  509.     if ((lTreeSubTicker >= 100)&&(mgetWnd != NULL)) 
  510.     {
  511.         sprintf(sTreeWriteHere,"%i",lTreeTicker);
  512.         SetWindowTitles(mgetWnd, szTickerString, (char *) ~0); 
  513.         lTreeSubTicker = 0;
  514.         lTreeTicker++;
  515.     }
  516.     lTreeSubTicker++;
  517.  
  518.     EXIT(TRUE)
  519. }
  520.  
  521.  
  522. void tree_mung(ppr_tree)
  523. tree    **ppr_tree;
  524. {
  525.     ENTER("tree_mung")
  526.     if (*ppr_tree)
  527.     {
  528.         tree_mung(&(**ppr_tree).tree_l);
  529.         tree_mung(&(**ppr_tree).tree_r);
  530.         free(*ppr_tree);
  531.  
  532.             if ((lTreeSubTicker >= 10)&&(mgetWnd != NULL))
  533.                 {
  534.                     sprintf(sTreeWriteHere,"%i",lTreeTicker);
  535.                     SetWindowTitles(mgetWnd, szTickerString, (char *) ~0);
  536.                     lTreeSubTicker = 0;
  537.                     lTreeTicker++;
  538.                 }
  539.             lTreeSubTicker++;
  540.  
  541.         *ppr_tree = NULL;
  542.     }
  543.     EXITV
  544. }
  545.